//电话号码的字母组合 力扣17
//回溯法 映射
class Solution {
public:
	string path;
	vector<string> ans;
	char ch[10][5];
	void backtracking(int len,int index,string digits)
	{
		if(path.size() == len)
		{
			ans.push_back(path);
			return;
		}
		int limit = (digits[index]-'0' == 7 || digits[index]-'0' == 9) ? 4 : 3;//控制边界
		for(int i = 1; i <= limit; i++)
		{
			path += (ch[digits[index]-'0'][i]);//处理本层
			backtracking(len,index+1,digits);//往下递归
			path.pop_back();//回溯  删除最后一位
		}
	}
	vector<string> letterCombinations(string digits) {
		int len = digits.size();
		if(len == 0) return {};
		//将字符数字与二位字符数组的层数作映射    
		char start = 'a';
		for(int i = 2; i <= 9; i++)
		{   
			int limit = (i == 7 || i == 9) ? 4 : 3;
			for(int j = 1; j <= limit; j++)
			{
				ch[i][j] = start++; 
			}
		}
		
		backtracking(len,0,digits);
		return ans;
	}
};
